package Leetcode第一期;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author : K k
 * @date : 9:08 2020/5/16
 */
public class 三数之和_15 {
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans=new ArrayList<>();
        Arrays.sort(nums);//从小到大排序
        if (nums.length<3||nums==null) return ans;
        int len=nums.length;

        for (int i=0;i<len;i++){
            if (nums[i]>0)break; //当数字大于0时 不满足条件
            if (i>0&&nums[i]==nums[i-1]) continue;
            int left=i+1;
            int right=len-1;
            while (left<right){
                int sum=nums[i]+nums[left]+nums[right];
                if (sum==0){
                    ans.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    while (left<right&&nums[left]==nums[left+1])left++;
                    while (left<right&&nums[right]==nums[right-1])right--;
                    left++;
                    right--;
                }
                else if(sum<0)left++;
                else if (sum>0)right--;
            }
        }
        return ans;

    }
}
